<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.10"/>
<title>Introduction_to_Algorithms: src/queue_algorithms/min_queue/minqueue.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
  $(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">Introduction_to_Algorithms
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.10 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
      <li><a href="globals.html"><span>File&#160;Members</span></a></li>
    </ul>
  </div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('minqueue_8h_source.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">minqueue.h</div>  </div>
</div><!--header-->
<div class="contents">
<a href="minqueue_8h.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno">    1</span>&#160;<span class="comment">/*</span></div>
<div class="line"><a name="l00002"></a><span class="lineno">    2</span>&#160;<span class="comment"> * Copyright 2016- huaxz &lt;huaxz1986@163.com&gt;</span></div>
<div class="line"><a name="l00003"></a><span class="lineno">    3</span>&#160;<span class="comment"> *</span></div>
<div class="line"><a name="l00004"></a><span class="lineno">    4</span>&#160;<span class="comment"> * This program is free software: you can redistribute it and/or modify</span></div>
<div class="line"><a name="l00005"></a><span class="lineno">    5</span>&#160;<span class="comment"> * it under the terms of the GNU General Public License as published by</span></div>
<div class="line"><a name="l00006"></a><span class="lineno">    6</span>&#160;<span class="comment"> * the Free Software Foundation, either version 2 of the License, or</span></div>
<div class="line"><a name="l00007"></a><span class="lineno">    7</span>&#160;<span class="comment"> * (at your option) any later version.</span></div>
<div class="line"><a name="l00008"></a><span class="lineno">    8</span>&#160;<span class="comment"> *</span></div>
<div class="line"><a name="l00009"></a><span class="lineno">    9</span>&#160;<span class="comment"> * This program is distributed in the hope that it will be useful,</span></div>
<div class="line"><a name="l00010"></a><span class="lineno">   10</span>&#160;<span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span></div>
<div class="line"><a name="l00011"></a><span class="lineno">   11</span>&#160;<span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span></div>
<div class="line"><a name="l00012"></a><span class="lineno">   12</span>&#160;<span class="comment"> * GNU General Public License for more details.</span></div>
<div class="line"><a name="l00013"></a><span class="lineno">   13</span>&#160;<span class="comment"> *</span></div>
<div class="line"><a name="l00014"></a><span class="lineno">   14</span>&#160;<span class="comment"> * You should have received a copy of the GNU General Public License</span></div>
<div class="line"><a name="l00015"></a><span class="lineno">   15</span>&#160;<span class="comment"> * along with this program.  If not, see &lt;http://www.gnu.org/licenses/&gt;.</span></div>
<div class="line"><a name="l00016"></a><span class="lineno">   16</span>&#160;<span class="comment"> *</span></div>
<div class="line"><a name="l00017"></a><span class="lineno">   17</span>&#160;<span class="comment"> * Author: huaxz1986@163.com (huaxz)</span></div>
<div class="line"><a name="l00018"></a><span class="lineno">   18</span>&#160;<span class="comment"> */</span></div>
<div class="line"><a name="l00019"></a><span class="lineno">   19</span>&#160;<span class="preprocessor">#ifndef MINQUEUE</span></div>
<div class="line"><a name="l00020"></a><span class="lineno">   20</span>&#160;<span class="preprocessor">#define MINQUEUE</span></div>
<div class="line"><a name="l00021"></a><span class="lineno">   21</span>&#160;<span class="preprocessor">#include&lt;vector&gt;</span></div>
<div class="line"><a name="l00022"></a><span class="lineno">   22</span>&#160;<span class="preprocessor">#include&lt;memory&gt;</span></div>
<div class="line"><a name="l00023"></a><span class="lineno">   23</span>&#160;<span class="preprocessor">#include&lt;functional&gt;</span></div>
<div class="line"><a name="l00024"></a><span class="lineno">   24</span>&#160;<span class="preprocessor">#include&quot;<a class="code" href="header_8h.html">src/header.h</a>&quot;</span></div>
<div class="line"><a name="l00025"></a><span class="lineno">   25</span>&#160;<span class="keyword">using</span> <a class="code" href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a19237111c3b1ec2717c5e1aefe2f6d9b">IntroductionToAlgorithm::GraphAlgorithm::unlimit</a>;</div>
<div class="line"><a name="l00026"></a><span class="lineno">   26</span>&#160;</div>
<div class="line"><a name="l00027"></a><span class="lineno">   27</span>&#160;<span class="keyword">namespace </span><a class="code" href="namespace_introduction_to_algorithm.html">IntroductionToAlgorithm</a></div>
<div class="line"><a name="l00028"></a><span class="lineno">   28</span>&#160;{</div>
<div class="line"><a name="l00029"></a><span class="lineno">   29</span>&#160;    <span class="keyword">namespace </span>QueueAlgorithm</div>
<div class="line"><a name="l00030"></a><span class="lineno">   30</span>&#160;    {</div>
<div class="line"><a name="l00031"></a><span class="lineno">   31</span>&#160;</div>
<div class="line"><a name="l00033"></a><span class="lineno">   33</span>&#160;</div>
<div class="line"><a name="l00059"></a><span class="lineno">   59</span>&#160;        <span class="keyword">template</span>&lt;<span class="keyword">typename</span> T,<span class="keyword">typename</span> TKeyType&gt;</div>
<div class="line"><a name="l00060"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html">   60</a></span>&#160;        <span class="keyword">class </span><a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html">MinQueue</a></div>
<div class="line"><a name="l00061"></a><span class="lineno">   61</span>&#160;        {</div>
<div class="line"><a name="l00062"></a><span class="lineno">   62</span>&#160;        <span class="keyword">public</span>:</div>
<div class="line"><a name="l00063"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">   63</a></span>&#160;            <span class="keyword">typedef</span> std::function&lt;bool (std::shared_ptr&lt;T&gt;,std::shared_ptr&lt;T&gt;)&gt; <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">CompareType</a> ; </div>
<div class="line"><a name="l00064"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">   64</a></span>&#160;            <span class="keyword">typedef</span> std::function&lt;TKeyType&amp;(std::shared_ptr&lt;T&gt;)&gt; <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">GetKeyType</a>; </div>
<div class="line"><a name="l00065"></a><span class="lineno">   65</span>&#160;</div>
<div class="line"><a name="l00071"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a98e54e4e2c19918032b09e23e79a25e5">   71</a></span>&#160;            <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a98e54e4e2c19918032b09e23e79a25e5">MinQueue</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">CompareType</a> compare,<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">GetKeyType</a> getKey):<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>(0),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>(compare),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>(getKey){}</div>
<div class="line"><a name="l00073"></a><span class="lineno">   73</span>&#160;</div>
<div class="line"><a name="l00079"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a770243b2227a15bdc2105dde6549c745">   79</a></span>&#160;            <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a770243b2227a15bdc2105dde6549c745">MinQueue</a>(std::size_t reseve_size,<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">CompareType</a> compare,<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">GetKeyType</a> getKey):<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>(0),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>(compare),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>(getKey)</div>
<div class="line"><a name="l00080"></a><span class="lineno">   80</span>&#160;            {</div>
<div class="line"><a name="l00081"></a><span class="lineno">   81</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.resize(reseve_size);</div>
<div class="line"><a name="l00082"></a><span class="lineno">   82</span>&#160;            }</div>
<div class="line"><a name="l00084"></a><span class="lineno">   84</span>&#160;</div>
<div class="line"><a name="l00092"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a96293074ee6adef713e9e47059958ea2">   92</a></span>&#160;            std::shared_ptr&lt;T&gt; <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a96293074ee6adef713e9e47059958ea2">min</a>()</div>
<div class="line"><a name="l00093"></a><span class="lineno">   93</span>&#160;            {</div>
<div class="line"><a name="l00094"></a><span class="lineno">   94</span>&#160;                <span class="keywordflow">if</span>(!<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>)</div>
<div class="line"><a name="l00095"></a><span class="lineno">   95</span>&#160;                    <span class="keywordflow">return</span> std::shared_ptr&lt;T&gt;();</div>
<div class="line"><a name="l00096"></a><span class="lineno">   96</span>&#160;                <span class="keywordflow">return</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[0];</div>
<div class="line"><a name="l00097"></a><span class="lineno">   97</span>&#160;            }</div>
<div class="line"><a name="l00099"></a><span class="lineno">   99</span>&#160;</div>
<div class="line"><a name="l00116"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a71022b9e1e9993ec5c5876da9e6e6eee">  116</a></span>&#160;            std::shared_ptr&lt;T&gt; <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a71022b9e1e9993ec5c5876da9e6e6eee">extract_min</a>()</div>
<div class="line"><a name="l00117"></a><span class="lineno">  117</span>&#160;            {</div>
<div class="line"><a name="l00118"></a><span class="lineno">  118</span>&#160;                <span class="keywordflow">if</span>(!<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>)</div>
<div class="line"><a name="l00119"></a><span class="lineno">  119</span>&#160;                    <span class="keywordflow">return</span> std::shared_ptr&lt;T&gt;();</div>
<div class="line"><a name="l00120"></a><span class="lineno">  120</span>&#160;                <span class="keyword">auto</span> result=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[0];</div>
<div class="line"><a name="l00121"></a><span class="lineno">  121</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[0]=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>-1];                </div>
<div class="line"><a name="l00122"></a><span class="lineno">  122</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>--;</div>
<div class="line"><a name="l00123"></a><span class="lineno">  123</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">heapify</a>(0);</div>
<div class="line"><a name="l00124"></a><span class="lineno">  124</span>&#160;                <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>&lt;=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.size()/4)</div>
<div class="line"><a name="l00125"></a><span class="lineno">  125</span>&#160;                    <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.resize(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>*2+2);</div>
<div class="line"><a name="l00126"></a><span class="lineno">  126</span>&#160;                <span class="keywordflow">return</span> result;</div>
<div class="line"><a name="l00127"></a><span class="lineno">  127</span>&#160;            }</div>
<div class="line"><a name="l00129"></a><span class="lineno">  129</span>&#160;</div>
<div class="line"><a name="l00148"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0992696959d7300082654529becd1765">  148</a></span>&#160;            <span class="keywordtype">int</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0992696959d7300082654529becd1765">insert</a>(std::shared_ptr&lt;T&gt; element)</div>
<div class="line"><a name="l00149"></a><span class="lineno">  149</span>&#160;            {</div>
<div class="line"><a name="l00150"></a><span class="lineno">  150</span>&#160;                <span class="keywordflow">if</span>(! element)  <span class="keywordflow">return</span> -1;</div>
<div class="line"><a name="l00151"></a><span class="lineno">  151</span>&#160;                <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>==<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.size()) <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.resize(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>*2+2);</div>
<div class="line"><a name="l00152"></a><span class="lineno">  152</span>&#160;                <span class="keywordtype">int</span> index=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>;</div>
<div class="line"><a name="l00153"></a><span class="lineno">  153</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>++;</div>
<div class="line"><a name="l00154"></a><span class="lineno">  154</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[index]=element;</div>
<div class="line"><a name="l00155"></a><span class="lineno">  155</span>&#160;                TKeyType&amp; k=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>(element);</div>
<div class="line"><a name="l00156"></a><span class="lineno">  156</span>&#160;                TKeyType old_k=k;</div>
<div class="line"><a name="l00157"></a><span class="lineno">  157</span>&#160;                k=unlimit&lt;TKeyType&gt;();</div>
<div class="line"><a name="l00158"></a><span class="lineno">  158</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#aa934049abcfedd59fa9ffe6d91fea30c">decreate_key</a>(index,old_k);</div>
<div class="line"><a name="l00159"></a><span class="lineno">  159</span>&#160;                <span class="keywordflow">return</span> index;</div>
<div class="line"><a name="l00160"></a><span class="lineno">  160</span>&#160;            }</div>
<div class="line"><a name="l00162"></a><span class="lineno">  162</span>&#160;</div>
<div class="line"><a name="l00170"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a1b484baf6cd011a4b91aa77a644e5a44">  170</a></span>&#160;            <span class="keywordtype">bool</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a1b484baf6cd011a4b91aa77a644e5a44">is_empty</a>()</div>
<div class="line"><a name="l00171"></a><span class="lineno">  171</span>&#160;            {</div>
<div class="line"><a name="l00172"></a><span class="lineno">  172</span>&#160;                <span class="keywordflow">return</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>==0;</div>
<div class="line"><a name="l00173"></a><span class="lineno">  173</span>&#160;            }</div>
<div class="line"><a name="l00174"></a><span class="lineno">  174</span>&#160;</div>
<div class="line"><a name="l00176"></a><span class="lineno">  176</span>&#160;</div>
<div class="line"><a name="l00185"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a545dbdb76e0b6e9c4227e558ab9b1239">  185</a></span>&#160;            <span class="keywordtype">int</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a545dbdb76e0b6e9c4227e558ab9b1239">index_inqueue</a>(std::shared_ptr&lt;T&gt; element)</div>
<div class="line"><a name="l00186"></a><span class="lineno">  186</span>&#160;            {</div>
<div class="line"><a name="l00187"></a><span class="lineno">  187</span>&#160;                <span class="keywordflow">if</span>(!element) <span class="keywordflow">throw</span> std::invalid_argument(<span class="stringliteral">&quot;is_inqueue error: element must not be nullptr!&quot;</span>);</div>
<div class="line"><a name="l00188"></a><span class="lineno">  188</span>&#160;                <span class="keywordflow">for</span>(std::size_t index=0;index&lt;<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>;index++)</div>
<div class="line"><a name="l00189"></a><span class="lineno">  189</span>&#160;                {</div>
<div class="line"><a name="l00190"></a><span class="lineno">  190</span>&#160;                    <span class="keywordflow">if</span>(element==<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>[index])</div>
<div class="line"><a name="l00191"></a><span class="lineno">  191</span>&#160;                        <span class="keywordflow">return</span> index;</div>
<div class="line"><a name="l00192"></a><span class="lineno">  192</span>&#160;                }</div>
<div class="line"><a name="l00193"></a><span class="lineno">  193</span>&#160;                <span class="keywordflow">return</span> -1;</div>
<div class="line"><a name="l00194"></a><span class="lineno">  194</span>&#160;            }</div>
<div class="line"><a name="l00196"></a><span class="lineno">  196</span>&#160;</div>
<div class="line"><a name="l00216"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#aa934049abcfedd59fa9ffe6d91fea30c">  216</a></span>&#160;            <span class="keywordtype">void</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#aa934049abcfedd59fa9ffe6d91fea30c">decreate_key</a>(std::size_t element_index,TKeyType new_key)</div>
<div class="line"><a name="l00217"></a><span class="lineno">  217</span>&#160;            {</div>
<div class="line"><a name="l00218"></a><span class="lineno">  218</span>&#160;                <span class="keywordflow">if</span>(element_index&gt;=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>)</div>
<div class="line"><a name="l00219"></a><span class="lineno">  219</span>&#160;                    <span class="keywordflow">throw</span> std::invalid_argument(<span class="stringliteral">&quot;decreate_key error: element_index must less than _size!&quot;</span>);</div>
<div class="line"><a name="l00220"></a><span class="lineno">  220</span>&#160;                <span class="keywordflow">if</span>(new_key&gt;<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(element_index)))</div>
<div class="line"><a name="l00221"></a><span class="lineno">  221</span>&#160;                    <span class="keywordflow">throw</span> std::invalid_argument(<span class="stringliteral">&quot;decreate_key error: new_key less _data.at(element_index)-&gt;key!&quot;</span>);</div>
<div class="line"><a name="l00222"></a><span class="lineno">  222</span>&#160;</div>
<div class="line"><a name="l00223"></a><span class="lineno">  223</span>&#160;                <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(element_index))=new_key;</div>
<div class="line"><a name="l00224"></a><span class="lineno">  224</span>&#160;                <span class="keywordtype">bool</span> valid;</div>
<div class="line"><a name="l00225"></a><span class="lineno">  225</span>&#160;                <span class="keywordflow">while</span>(element_index!=0 )</div>
<div class="line"><a name="l00226"></a><span class="lineno">  226</span>&#160;                {</div>
<div class="line"><a name="l00227"></a><span class="lineno">  227</span>&#160;                    <span class="keyword">auto</span> pIndex=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3b7cac401c8cf45806e61aad3799eda0">_parentIndex</a>(element_index,valid);</div>
<div class="line"><a name="l00228"></a><span class="lineno">  228</span>&#160;                    <span class="keywordflow">if</span>(!valid) <span class="keywordflow">break</span>;</div>
<div class="line"><a name="l00229"></a><span class="lineno">  229</span>&#160;                    <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(pIndex),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(element_index))) <span class="keywordflow">break</span>;</div>
<div class="line"><a name="l00230"></a><span class="lineno">  230</span>&#160;                    std::swap(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(pIndex),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(element_index));</div>
<div class="line"><a name="l00231"></a><span class="lineno">  231</span>&#160;                    element_index=pIndex;</div>
<div class="line"><a name="l00232"></a><span class="lineno">  232</span>&#160;                }</div>
<div class="line"><a name="l00233"></a><span class="lineno">  233</span>&#160;            }</div>
<div class="line"><a name="l00235"></a><span class="lineno">  235</span>&#160;</div>
<div class="line"><a name="l00243"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a9a432c7c167a4f9a56c2988cfdc04620">  243</a></span>&#160;            <span class="keywordtype">void</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a9a432c7c167a4f9a56c2988cfdc04620">setupHeap</a>()</div>
<div class="line"><a name="l00244"></a><span class="lineno">  244</span>&#160;            {</div>
<div class="line"><a name="l00245"></a><span class="lineno">  245</span>&#160;                <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>&lt;=1)</div>
<div class="line"><a name="l00246"></a><span class="lineno">  246</span>&#160;                    <span class="keywordflow">return</span>;</div>
<div class="line"><a name="l00247"></a><span class="lineno">  247</span>&#160;                <span class="keywordtype">int</span> index=(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>-1)/2;</div>
<div class="line"><a name="l00248"></a><span class="lineno">  248</span>&#160;                <span class="keywordflow">while</span>(index&gt;=0)</div>
<div class="line"><a name="l00249"></a><span class="lineno">  249</span>&#160;                {</div>
<div class="line"><a name="l00250"></a><span class="lineno">  250</span>&#160;                    <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">heapify</a>(index);</div>
<div class="line"><a name="l00251"></a><span class="lineno">  251</span>&#160;                    index--;</div>
<div class="line"><a name="l00252"></a><span class="lineno">  252</span>&#160;                }</div>
<div class="line"><a name="l00253"></a><span class="lineno">  253</span>&#160;            }</div>
<div class="line"><a name="l00255"></a><span class="lineno">  255</span>&#160;</div>
<div class="line"><a name="l00265"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">  265</a></span>&#160;            <span class="keywordtype">void</span> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">heapify</a>(std::size_t elementIndex)</div>
<div class="line"><a name="l00266"></a><span class="lineno">  266</span>&#160;            {</div>
<div class="line"><a name="l00267"></a><span class="lineno">  267</span>&#160;                <span class="keywordflow">if</span>(elementIndex&gt;=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>)</div>
<div class="line"><a name="l00268"></a><span class="lineno">  268</span>&#160;                    <span class="keywordflow">return</span>;</div>
<div class="line"><a name="l00269"></a><span class="lineno">  269</span>&#160;                <span class="keyword">auto</span> minIndex=elementIndex;</div>
<div class="line"><a name="l00270"></a><span class="lineno">  270</span>&#160;                <span class="keywordtype">bool</span> left_valid=<span class="keyword">true</span>;</div>
<div class="line"><a name="l00271"></a><span class="lineno">  271</span>&#160;                <span class="keywordtype">bool</span> right_valid=<span class="keyword">true</span>;</div>
<div class="line"><a name="l00272"></a><span class="lineno">  272</span>&#160;                <span class="keyword">auto</span> leftIndex=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0d2a517cd63fc33c0403a4d4c83c7e9d">_lchildIndex</a>(elementIndex,left_valid);</div>
<div class="line"><a name="l00273"></a><span class="lineno">  273</span>&#160;                <span class="keyword">auto</span> rightIndex=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a7129becd0fd74b5d2c17702e65f32300">_rchildIndex</a>(elementIndex,right_valid);</div>
<div class="line"><a name="l00274"></a><span class="lineno">  274</span>&#160;</div>
<div class="line"><a name="l00275"></a><span class="lineno">  275</span>&#160;                <span class="keywordflow">if</span>(left_valid)</div>
<div class="line"><a name="l00276"></a><span class="lineno">  276</span>&#160;                {</div>
<div class="line"><a name="l00277"></a><span class="lineno">  277</span>&#160;                    <span class="keywordflow">if</span>( <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(leftIndex),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(minIndex)))</div>
<div class="line"><a name="l00278"></a><span class="lineno">  278</span>&#160;                        minIndex=leftIndex;</div>
<div class="line"><a name="l00279"></a><span class="lineno">  279</span>&#160;                }</div>
<div class="line"><a name="l00280"></a><span class="lineno">  280</span>&#160;                <span class="keywordflow">if</span>(right_valid)</div>
<div class="line"><a name="l00281"></a><span class="lineno">  281</span>&#160;                {</div>
<div class="line"><a name="l00282"></a><span class="lineno">  282</span>&#160;                    <span class="keywordflow">if</span>( <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(rightIndex),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(minIndex)))</div>
<div class="line"><a name="l00283"></a><span class="lineno">  283</span>&#160;                        minIndex=rightIndex;</div>
<div class="line"><a name="l00284"></a><span class="lineno">  284</span>&#160;                }</div>
<div class="line"><a name="l00285"></a><span class="lineno">  285</span>&#160;                <span class="keywordflow">if</span>(minIndex!=elementIndex)</div>
<div class="line"><a name="l00286"></a><span class="lineno">  286</span>&#160;                {</div>
<div class="line"><a name="l00287"></a><span class="lineno">  287</span>&#160;                    std::swap(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(elementIndex),<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>.at(minIndex));</div>
<div class="line"><a name="l00288"></a><span class="lineno">  288</span>&#160;                    <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">heapify</a>(minIndex);</div>
<div class="line"><a name="l00289"></a><span class="lineno">  289</span>&#160;                }</div>
<div class="line"><a name="l00290"></a><span class="lineno">  290</span>&#160;            }</div>
<div class="line"><a name="l00291"></a><span class="lineno">  291</span>&#160;       <span class="keyword">protected</span>:</div>
<div class="line"><a name="l00293"></a><span class="lineno">  293</span>&#160;</div>
<div class="line"><a name="l00303"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3b7cac401c8cf45806e61aad3799eda0">  303</a></span>&#160;            std::size_t <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3b7cac401c8cf45806e61aad3799eda0">_parentIndex</a>(std::size_t elementIndex,<span class="keywordtype">bool</span>&amp; valid)</div>
<div class="line"><a name="l00304"></a><span class="lineno">  304</span>&#160;            {</div>
<div class="line"><a name="l00305"></a><span class="lineno">  305</span>&#160;                <span class="keywordflow">if</span>(elementIndex&gt;=<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>)</div>
<div class="line"><a name="l00306"></a><span class="lineno">  306</span>&#160;                {</div>
<div class="line"><a name="l00307"></a><span class="lineno">  307</span>&#160;                    valid=<span class="keyword">false</span>; <span class="comment">//无效结果</span></div>
<div class="line"><a name="l00308"></a><span class="lineno">  308</span>&#160;                    <span class="keywordflow">return</span> 0;</div>
<div class="line"><a name="l00309"></a><span class="lineno">  309</span>&#160;                }</div>
<div class="line"><a name="l00310"></a><span class="lineno">  310</span>&#160;                valid=<span class="keyword">true</span>; <span class="comment">//有效结果</span></div>
<div class="line"><a name="l00311"></a><span class="lineno">  311</span>&#160;                <span class="keywordflow">if</span> (elementIndex ==0) <span class="keywordflow">return</span> 0; <span class="comment">//根节点的父节点是自己</span></div>
<div class="line"><a name="l00312"></a><span class="lineno">  312</span>&#160;                <span class="keywordflow">else</span>  <span class="keywordflow">return</span> (elementIndex-1)&gt;&gt;1;</div>
<div class="line"><a name="l00313"></a><span class="lineno">  313</span>&#160;            }</div>
<div class="line"><a name="l00315"></a><span class="lineno">  315</span>&#160;</div>
<div class="line"><a name="l00326"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0d2a517cd63fc33c0403a4d4c83c7e9d">  326</a></span>&#160;            std::size_t <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0d2a517cd63fc33c0403a4d4c83c7e9d">_lchildIndex</a>(std::size_t elementIndex,<span class="keywordtype">bool</span>&amp; valid)</div>
<div class="line"><a name="l00327"></a><span class="lineno">  327</span>&#160;            {</div>
<div class="line"><a name="l00328"></a><span class="lineno">  328</span>&#160;                <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>&lt;2)</div>
<div class="line"><a name="l00329"></a><span class="lineno">  329</span>&#160;                {</div>
<div class="line"><a name="l00330"></a><span class="lineno">  330</span>&#160;                    valid=<span class="keyword">false</span>; <span class="comment">//数组元素太少无效结果</span></div>
<div class="line"><a name="l00331"></a><span class="lineno">  331</span>&#160;                    <span class="keywordflow">return</span> 0;</div>
<div class="line"><a name="l00332"></a><span class="lineno">  332</span>&#160;                }</div>
<div class="line"><a name="l00333"></a><span class="lineno">  333</span>&#160;                <span class="keywordflow">if</span>(  elementIndex&gt;((<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>-2)&gt;&gt;1)  )</div>
<div class="line"><a name="l00334"></a><span class="lineno">  334</span>&#160;                {</div>
<div class="line"><a name="l00335"></a><span class="lineno">  335</span>&#160;                    valid=<span class="keyword">false</span>;<span class="comment">//超出范围，无效</span></div>
<div class="line"><a name="l00336"></a><span class="lineno">  336</span>&#160;                    <span class="keywordflow">return</span> 0;</div>
<div class="line"><a name="l00337"></a><span class="lineno">  337</span>&#160;                }</div>
<div class="line"><a name="l00338"></a><span class="lineno">  338</span>&#160;                valid=<span class="keyword">true</span>;</div>
<div class="line"><a name="l00339"></a><span class="lineno">  339</span>&#160;                <span class="keywordflow">return</span> (elementIndex&lt;&lt;1)+1;</div>
<div class="line"><a name="l00340"></a><span class="lineno">  340</span>&#160;            }</div>
<div class="line"><a name="l00342"></a><span class="lineno">  342</span>&#160;</div>
<div class="line"><a name="l00353"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a7129becd0fd74b5d2c17702e65f32300">  353</a></span>&#160;            std::size_t <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a7129becd0fd74b5d2c17702e65f32300">_rchildIndex</a>(std::size_t elementIndex,<span class="keywordtype">bool</span>&amp; valid)</div>
<div class="line"><a name="l00354"></a><span class="lineno">  354</span>&#160;            {</div>
<div class="line"><a name="l00355"></a><span class="lineno">  355</span>&#160;                <span class="keywordflow">if</span>(<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>&lt;3)</div>
<div class="line"><a name="l00356"></a><span class="lineno">  356</span>&#160;                {</div>
<div class="line"><a name="l00357"></a><span class="lineno">  357</span>&#160;                    valid=<span class="keyword">false</span>; <span class="comment">//数组元素太少无效结果</span></div>
<div class="line"><a name="l00358"></a><span class="lineno">  358</span>&#160;                    <span class="keywordflow">return</span> 0;</div>
<div class="line"><a name="l00359"></a><span class="lineno">  359</span>&#160;                }</div>
<div class="line"><a name="l00360"></a><span class="lineno">  360</span>&#160;                <span class="keywordflow">if</span>(  elementIndex&gt;((<a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>-3)&gt;&gt;1)  )</div>
<div class="line"><a name="l00361"></a><span class="lineno">  361</span>&#160;                {</div>
<div class="line"><a name="l00362"></a><span class="lineno">  362</span>&#160;                    valid=<span class="keyword">false</span>;<span class="comment">//超出范围，无效</span></div>
<div class="line"><a name="l00363"></a><span class="lineno">  363</span>&#160;                    <span class="keywordflow">return</span> 0;</div>
<div class="line"><a name="l00364"></a><span class="lineno">  364</span>&#160;                }</div>
<div class="line"><a name="l00365"></a><span class="lineno">  365</span>&#160;                valid=<span class="keyword">true</span>;</div>
<div class="line"><a name="l00366"></a><span class="lineno">  366</span>&#160;                <span class="keywordflow">return</span> (elementIndex&lt;&lt;1)+2;</div>
<div class="line"><a name="l00367"></a><span class="lineno">  367</span>&#160;            }</div>
<div class="line"><a name="l00368"></a><span class="lineno">  368</span>&#160;        <span class="keyword">private</span>:</div>
<div class="line"><a name="l00369"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">  369</a></span>&#160;            std::vector&lt;std::shared_ptr&lt;T&gt;&gt; <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">_data</a>;  </div>
<div class="line"><a name="l00370"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">  370</a></span>&#160;            std::size_t <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">_size</a>;  </div>
<div class="line"><a name="l00371"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">  371</a></span>&#160;            <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">CompareType</a> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">_compare</a>;  </div>
<div class="line"><a name="l00372"></a><span class="lineno"><a class="line" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">  372</a></span>&#160;            <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">GetKeyType</a> <a class="code" href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">_getKey</a>; </div>
<div class="line"><a name="l00373"></a><span class="lineno">  373</span>&#160;        };</div>
<div class="line"><a name="l00374"></a><span class="lineno">  374</span>&#160;    }</div>
<div class="line"><a name="l00375"></a><span class="lineno">  375</span>&#160;}</div>
<div class="line"><a name="l00376"></a><span class="lineno">  376</span>&#160;<span class="preprocessor">#endif // MINQUEUE</span></div>
<div class="line"><a name="l00377"></a><span class="lineno">  377</span>&#160;</div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a5de60762d317fc92c18e882dd50f8dfa"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a5de60762d317fc92c18e882dd50f8dfa">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_compare</a></div><div class="ttdeci">CompareType _compare</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00371">minqueue.h:371</a></div></div>
<div class="ttc" id="header_8h_html"><div class="ttname"><a href="header_8h.html">header.h</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a8f2f5b5d2b7097bbc6edda7b9c9228a6"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a8f2f5b5d2b7097bbc6edda7b9c9228a6">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::CompareType</a></div><div class="ttdeci">std::function&lt; bool(std::shared_ptr&lt; T &gt;, std::shared_ptr&lt; T &gt;)&gt; CompareType</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00063">minqueue.h:63</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a3f791f9dd9d61dc2caf1d6b2b354f4c4"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3f791f9dd9d61dc2caf1d6b2b354f4c4">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_getKey</a></div><div class="ttdeci">GetKeyType _getKey</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00372">minqueue.h:372</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a96293074ee6adef713e9e47059958ea2"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a96293074ee6adef713e9e47059958ea2">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::min</a></div><div class="ttdeci">std::shared_ptr&lt; T &gt; min()</div><div class="ttdoc">min:返回最小值 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00092">minqueue.h:92</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a71022b9e1e9993ec5c5876da9e6e6eee"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a71022b9e1e9993ec5c5876da9e6e6eee">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::extract_min</a></div><div class="ttdeci">std::shared_ptr&lt; T &gt; extract_min()</div><div class="ttdoc">extract_min:删除队列中最小值，并返回最小值 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00116">minqueue.h:116</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html">IntroductionToAlgorithm::QueueAlgorithm::MinQueue</a></div><div class="ttdoc">MinQueue：最小优先级队列，算法导论第6章6.5节 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00060">minqueue.h:60</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_ad463395cef741624e6d078e4e4fc624f"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#ad463395cef741624e6d078e4e4fc624f">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_data</a></div><div class="ttdeci">std::vector&lt; std::shared_ptr&lt; T &gt; &gt; _data</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00369">minqueue.h:369</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a98e54e4e2c19918032b09e23e79a25e5"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a98e54e4e2c19918032b09e23e79a25e5">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::MinQueue</a></div><div class="ttdeci">MinQueue(CompareType compare, GetKeyType getKey)</div><div class="ttdoc">显式构造函数 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00071">minqueue.h:71</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a3b7cac401c8cf45806e61aad3799eda0"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a3b7cac401c8cf45806e61aad3799eda0">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_parentIndex</a></div><div class="ttdeci">std::size_t _parentIndex(std::size_t elementIndex, bool &amp;valid)</div><div class="ttdoc">_parentIndex:返回一个节点的父节点位置 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00303">minqueue.h:303</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a7129becd0fd74b5d2c17702e65f32300"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a7129becd0fd74b5d2c17702e65f32300">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_rchildIndex</a></div><div class="ttdeci">std::size_t _rchildIndex(std::size_t elementIndex, bool &amp;valid)</div><div class="ttdoc">_rchildIndex:返回一个节点的右子节点位置 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00353">minqueue.h:353</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a0de92802e37516dda2c01de776aba641"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0de92802e37516dda2c01de776aba641">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_size</a></div><div class="ttdeci">std::size_t _size</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00370">minqueue.h:370</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a770243b2227a15bdc2105dde6549c745"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a770243b2227a15bdc2105dde6549c745">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::MinQueue</a></div><div class="ttdeci">MinQueue(std::size_t reseve_size, CompareType compare, GetKeyType getKey)</div><div class="ttdoc">显式构造函数 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00079">minqueue.h:79</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a545dbdb76e0b6e9c4227e558ab9b1239"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a545dbdb76e0b6e9c4227e558ab9b1239">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::index_inqueue</a></div><div class="ttdeci">int index_inqueue(std::shared_ptr&lt; T &gt; element)</div><div class="ttdoc">is_inqueue:返回指定元素是否在队列中 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00185">minqueue.h:185</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_aa934049abcfedd59fa9ffe6d91fea30c"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#aa934049abcfedd59fa9ffe6d91fea30c">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::decreate_key</a></div><div class="ttdeci">void decreate_key(std::size_t element_index, TKeyType new_key)</div><div class="ttdoc">decreate_key:缩减队列中某个元素的key </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00216">minqueue.h:216</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a0992696959d7300082654529becd1765"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0992696959d7300082654529becd1765">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::insert</a></div><div class="ttdeci">int insert(std::shared_ptr&lt; T &gt; element)</div><div class="ttdoc">insert:向队列中插入一个元素 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00148">minqueue.h:148</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a4ddfab80f781d5b5f7544164bf266f82"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a4ddfab80f781d5b5f7544164bf266f82">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::heapify</a></div><div class="ttdeci">void heapify(std::size_t elementIndex)</div><div class="ttdoc">heapify：维持堆性质 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00265">minqueue.h:265</a></div></div>
<div class="ttc" id="namespace_introduction_to_algorithm_1_1_graph_algorithm_html_a19237111c3b1ec2717c5e1aefe2f6d9b"><div class="ttname"><a href="namespace_introduction_to_algorithm_1_1_graph_algorithm.html#a19237111c3b1ec2717c5e1aefe2f6d9b">IntroductionToAlgorithm::GraphAlgorithm::unlimit</a></div><div class="ttdeci">T unlimit()</div><div class="ttdoc">unlimit：返回正无穷的函数 </div><div class="ttdef"><b>Definition:</b> <a href="header_8h_source.html#l00111">header.h:111</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a0d2a517cd63fc33c0403a4d4c83c7e9d"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a0d2a517cd63fc33c0403a4d4c83c7e9d">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::_lchildIndex</a></div><div class="ttdeci">std::size_t _lchildIndex(std::size_t elementIndex, bool &amp;valid)</div><div class="ttdoc">_lchildIndex:返回一个节点的左子节点位置 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00326">minqueue.h:326</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a391cb754ab172d1d4cdefd34130b917c"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a391cb754ab172d1d4cdefd34130b917c">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::GetKeyType</a></div><div class="ttdeci">std::function&lt; TKeyType &amp;(std::shared_ptr&lt; T &gt;)&gt; GetKeyType</div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00064">minqueue.h:64</a></div></div>
<div class="ttc" id="namespace_introduction_to_algorithm_html"><div class="ttname"><a href="namespace_introduction_to_algorithm.html">IntroductionToAlgorithm</a></div><div class="ttdoc">Namespace of IntrodunctionToAlgorithm. </div><div class="ttdef"><b>Definition:</b> <a href="longest__common__subsequence_8h_source.html#l00024">longest_common_subsequence.h:24</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a1b484baf6cd011a4b91aa77a644e5a44"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a1b484baf6cd011a4b91aa77a644e5a44">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::is_empty</a></div><div class="ttdeci">bool is_empty()</div><div class="ttdoc">is_empty:返回队列是否为空 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00170">minqueue.h:170</a></div></div>
<div class="ttc" id="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue_html_a9a432c7c167a4f9a56c2988cfdc04620"><div class="ttname"><a href="class_introduction_to_algorithm_1_1_queue_algorithm_1_1_min_queue.html#a9a432c7c167a4f9a56c2988cfdc04620">IntroductionToAlgorithm::QueueAlgorithm::MinQueue::setupHeap</a></div><div class="ttdeci">void setupHeap()</div><div class="ttdoc">setupHeap:建堆 </div><div class="ttdef"><b>Definition:</b> <a href="minqueue_8h_source.html#l00243">minqueue.h:243</a></div></div>
</div><!-- fragment --></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="dir_8ed9dba4cd616b67da9b1338594e34e0.html">src</a></li><li class="navelem"><a class="el" href="dir_b144fdcc7226fc970a6ccdd8bb1f9004.html">queue_algorithms</a></li><li class="navelem"><a class="el" href="dir_28335c281b58f87353fdbfb23e024a8a.html">min_queue</a></li><li class="navelem"><a class="el" href="minqueue_8h.html">minqueue.h</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.10 </li>
  </ul>
</div>
</body>
</html>
